package com.ai.zuochengyun.phase01.class01;

import java.util.*;

/**
 * 线段最大重合问题
 */
public class Code14_CoverMax {

    public static void main(String[] args) {
        System.out.println("开始统计");
        for (int i = 0; i < 10000; i++) {
            List<LineSegment> lines1 = new ArrayList<>(64);
            List<LineSegment> lines2 = new ArrayList<>(64);

            int size = (int)(Math.random()*10+1)+4;
            for (int j = 0; j < size; j++) {
                int a = (int)(Math.random()*10+1)*3;
                int b = (int)(Math.random()*10+1)*5;
                int start = Math.min(a, b);
                int end = Math.max(a, b);
                if (start == end) {
                    end++;
                }

                LineSegment lineSegment = new LineSegment(start, end);
                lines1.add(lineSegment);
                LineSegment lineSegment2 = new LineSegment(start, end);
                lines2.add(lineSegment2);
            }

            int i1 = maxCover(lines1);
            int i2 = test(lines2);
            if (i1 != i2) {
                System.out.println("oops, 结果计算错误"+", i1="+i1+", i2="+i2);
                for (int k = 0; k < lines1.size(); k++) {
                    System.out.print(lines1.get(k).toString() + " ");
                }
                break;
            }
        }
        System.out.println();
        System.out.println("结束统计");
    }

    /**
     * 暴力解法
     * @param lines
     * @return
     */
    public static int test(List<LineSegment> lines) {
        if (lines.isEmpty()) {
            return 0;
        }
        if (lines.size() == 1) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < lines.size(); i++) {
            min = Math.min(min, lines.get(i).start);
            max = Math.max(max, lines.get(i).end);
        }

        int res = 0;
        for (double p = min +0.5; p < max; p+= 1) {
            int cur = 0;
            // 遍历所有的线段在覆盖当前点的个数
            for (int i = 0; i < lines.size(); i++) {
                // 因为是用1作为线段的分段，那么线段肯定会覆盖0.5的位置
                // 只要当前线段覆盖到了该点，就+1
                if (lines.get(i).start < p && lines.get(i).end > p) {
                    cur++;
                }
            }
            res = Math.max(res, cur);
        }
        return res;
    }

    /**
     * 小根堆实现
     * @param lines
     * @return
     */
    private static int maxCover(List<LineSegment> lines) {
        if (lines.isEmpty()) {
            return 0;
        }
        if (lines.size() == 1) {
            return 1;
        }

        lines.sort((o1, o2) -> o1.start - o2.start);
        PriorityQueue<Integer> endEleHeap = new PriorityQueue<>();
        int res = 0;
        for (int i = 0; i < lines.size(); i++) {
            LineSegment cur = lines.get(i);
            // 校验结尾元素所在的小根堆中是否有元素
            // 结尾位置小于等于线段开始的位置，那么表示不会贯穿该线段，需要移除
            while (!endEleHeap.isEmpty() && endEleHeap.peek() <= cur.start) {
                endEleHeap.poll();
            }
            endEleHeap.add(cur.end);

            // 线段重合最多的，即为覆盖度最大的数
            res = Math.max(res, endEleHeap.size());
        }
        return res;
    }


    private static class LineSegment {
        public int start;

        public int end;

        public LineSegment(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "["+start+", "+end+"]";
        }
    }

}
